package com.aqie.easy.string;

import java.util.LinkedList;

/**
 * 38 报数 TODO 尾递归
 */
public class CountAndSay {
    /**
     * 1. 9ms
     * @param n
     * @return
     */
    public String countAndSay(int n) {
        return countHelper("1", n);
    }

    /**
     * 尾递归
     * @param str
     * @param n
     * @return
     */
    private static String countHelper(String str, int n) {
        if (n == 1) return str;
        else {
            //求下一个数
            StringBuilder stringBuilder = new StringBuilder();
            int i = 0;
            //一直读数
            while (i < str.length()) {
                int count = 1;
                //如果一直是同一个数
                while (i < str.length() - 1 && str.charAt(i) == str.charAt(i + 1)) {
                    count++;
                    i++;
                }
                //下一个数更新
                stringBuilder.append(Integer.toString(count) + str.charAt(i));
                i++;
            }
            str = stringBuilder.toString();
        }
        return countHelper(str, n - 1);
    }

    /**
     * 2. 队列  9ms
     * @param n
     * @return
     */
    public String countAndSay2(int n) {
        if (n==1){
            return "1";
        }
        LinkedList<Integer> queue = new LinkedList<>();
        // 计数
        int count = 0;
        // 标记
        int temp;
        queue.addLast(1);
        for (int i = 0; i < n-1; i++) {
            temp = queue.getFirst();
            int len = queue.size();
            for (int j = 0; j < len; j++) {
                // 取出一个元素
                Integer poll = queue.poll();
                if (poll != temp){
                    queue.addLast(count);
                    queue.addLast(temp);
                    temp = poll;
                    // 因为已经取了一个,count自动加1
                    count=1;
                }else{
                    count++;
                }
            }
            queue.addLast(count);
            queue.addLast(temp);
            count=0;
        }

        StringBuilder sb = new StringBuilder();
        for (Integer integer:
                queue) {
            sb.append(integer);
        }

        return sb.toString();
    }


    /**
     * 3.直抒胸臆 5ms
     */
    public String countAndSay3(int n) {
        if(n==1)
            return "1";
        else
            return process("11",n-2);

    }
    String process(String s1,int count){
        if(count==0)
            return s1;
        StringBuilder s2= new StringBuilder();
        int len1=s1.length();
        for(int i=0;i<len1;){
            int k=1;
            while(k+i<len1){
                if(s1.charAt(i)==s1.charAt(k+i)){
                    k++;
                }
                else{
                    break;
                }
            }
            s2.append(k).append(s1.charAt(i));
            i=i+k;
        }
        return process(s2.toString(),count-1);
    }

    /**
     * 4. 双指针 5ms
     * @param n
     * @return
     */
    public String countAndSay4(int n) {

        if(n<1||n>30){
            throw new IllegalArgumentException("parameter error");
        }

        StringBuilder str = new StringBuilder("1");
        for(int i=1;i<n;i++){

            char[] chs = str.toString().toCharArray();

            int first=0,second=1;
            str = new StringBuilder();
            while(second<chs.length){
                if(chs[first]!=chs[second]){
                    str.append(String.valueOf(second - first)).append(chs[first]);
                    first = second;
                }
                second++;
            }
            str.append(String.valueOf(second - first)).append(chs[first]);
        }

        return str.toString();
    }

    /**
     * 双指针 + 递归 3ms
     * @param n
     * @return
     */
    public String countAndSay5(int n) {
        if(n == 1) return "1";

        String str = countAndSay5(n-1);
        int len = str.length();
        StringBuilder builder = new StringBuilder();
        for(int i=0,j=0; i<len;){
            int count = 0;
            while(i<len && str.charAt(j) == str.charAt(i)){
                i++;
                count++;
            }
            builder.append(count).append(str.charAt(j));
            j = i;
        }

        return builder.toString();
    }


}
